package advanced.class_append;

import java.util.Stack;

// 给定二维数组，求二维数组中最大的矩形面积
// LeeCode85题
public class Code_04_MaxArea {

    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int[] heights = new int[col];
        int maxArea = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                heights[j] = matrix[i][j] == '0' ? 0 : heights[j] + 1;
            }
            maxArea = Math.max(maxArea,getMaxArea(heights));
        }
        return maxArea;
    }

    /**
     * 给定一个直方图的数组，求该直方图中最大的矩形面积
     * @param heights
     * @return
     */
    private int getMaxArea(int[] heights) {
        // 这里不进行边界判断了，交给主函数
        // 创建单调栈
        Stack<Integer> stack = new Stack<Integer>();
        int index = 0;
        int maxArea = 0;
        while(index < heights.length){
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[index]){
                int h = stack.pop();
                int l = stack.isEmpty() ? -1 : stack.peek();
                maxArea = Math.max(maxArea,(index - l - 1) * heights[h]);
            }
            stack.push(index++);
        }
        while(!stack.isEmpty()){
            int h =stack.pop();
            int l = stack.isEmpty() ? -1 : stack.peek();
            maxArea = Math.max(maxArea,(index - l - 1) * heights[h]);
        }
        return maxArea;
    }
}
